import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        dfs(A, B, C, A.size());
        // Collections.reverse(C);
    }

    /**
     * 将 n 个圆盘借助 b 从 a 移动到 c 上
     * @param a
     * @param b
     * @param c
     * @param n
     */
    public void dfs(List<Integer> a, List<Integer> b, List<Integer> c, int n) {
        // 递归出口
        if (n <= 1) {
            c.add(a.remove(a.size() - 1));
            return;
        }
        // 继续递归
        // 1. 将 n - 1 个圆盘借助 c 从 a 移动到 b 上
        dfs(a, c, b, n - 1);
        // 2. 将 第 n 个圆盘移动到 C 上
        c.add(a.remove(a.size() - 1));
        // 3. 将 n - 1 个圆盘借助 a 从 b 移动到 C 上
        dfs(b, a, c, n - 1);
    }

    public static class ListNode {
        int val;
        ListNode next;
        public ListNode(int val) {
            this.val = val;
        }
    }

    /**
     * 合并两个有序链表
     */
    ListNode head = new ListNode(-1);
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode cur = head;
        dfs(list1, list2, cur);
        return head.next;
    }

    public void dfs(ListNode list1, ListNode list2, ListNode cur) {
        // 递归出口
        if (list1 == null) {
            cur.next = list2;
            return;
        }
        if (list2 == null) {
            cur.next = list1;
            return;
        }
        // 继续递归
        if (list1.val < list2.val) {
            cur.next = list1;
            list1 = list1.next;
        } else {
            cur.next = list2;
            list2 = list2.next;
        }
        cur = cur.next;
        dfs(list1, list2, cur);
    }

    /**
     * 反转链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        // 递归出口
        if (head == null || head.next == null) {
            return head;
        }
        // 继续递归
        // 1. 逆序当前节点之后的节点
        ListNode newHead = reverseList(head.next);
        // 2. 将当前节点加入到逆序之后的链表
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    /**
     * 两两交换链表中的节点
     * @param head
     * @return
     */
    public ListNode swapPairs(ListNode head) {
        // 递归出口(无节点或只有一个单节点)
        if (head == null || head.next == null) {
            return head;
        }
        // 继续递归
        // 1. 对后面节点进行交换
        ListNode newHead = swapPairs(head.next.next);
        // 2. 交换当前两节点
        ListNode tmp = head;
        head = head.next;
        head.next = tmp;
        tmp.next = newHead;
        return head;
    }

    /**
     * Pow(x, n)
     * @param x
     * @param n
     * @return
     */
    public double myPow(double x, int n) {
        int flg = n > 0 ? 1: -1;
        double ret = dfs(x, n * flg);
        return flg == 1 ? ret : 1 / ret;
    }
    public double dfs(double x, int n) {
        // 递归出口
        if (n == 0) {
            return 1;
        }
        if (n == 1) {
            return x;
        }
        // 继续递归
        double tmp = dfs(x, n / 2);
        if (n % 2 == 0) {
            return tmp * tmp;
        } else {
            return tmp * tmp * x;
        }
    }


    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * 计算布尔二叉树的值
     * @param root
     * @return
     */
    public boolean evaluateTree(TreeNode root) {
        // 递归出口
        if (root.val == 0) {
            return false;
        }
        if (root.val == 1) {
            return true;
        }
        // 继续递归
        boolean left = evaluateTree(root.left);
        boolean right = evaluateTree(root.right);
        if (root.val == 2) {
            return (left | right);
        } else {
            return (left & right);
        }
    }

    /**
     * 求根节点到叶节点数字之和
     * @param root
     * @return
     */
    public int sumNumbers(TreeNode root) {
        return dfs(root, 0);
    }
    public int dfs(TreeNode root, int num) {
        int prevSum = num * 10 + root.val;
        // 递归出口
        if (root.left == null && root.right == null) {
            return prevSum;
        }
        // 继续递归
        int ret = 0;
        if (root.left != null) {
            ret += dfs(root.left, prevSum);
        }
        if (root.right != null) {
            ret += dfs(root.right, prevSum);
        }
        return ret;
    }

    /**
     * 二叉树剪枝
     * @param root
     * @return
     */
    public TreeNode pruneTree(TreeNode root) {
        return dfs(root) > 0 ? root : null;
    }

    public int dfs(TreeNode root) {
        // 递归出口
        if (root == null) {
            return 0;
        }
        if (root.left == null && root.right == null) {
            return root.val;
        }
        // 1. 继续递归
        int left = dfs(root.left);
        int right = dfs(root.right);
        // 2. 剪枝
        if (left == 0) {
            root.left = null;
        }
        if (right == 0) {
            root.right = null;
        }
        return root.val + left + right;
    }

    // 前驱节点
    long prev = Long.MIN_VALUE;

    /**
     * 验证二叉搜索树
     * @param root
     * @return
     */
    // 进行中序遍历
    public boolean isValidBST(TreeNode root) {
        // 递归出口
        if (root == null) {
            return true;
        }
        // 继续递归
        boolean left = isValidBST(root.left);
        // 剪枝
        if (!left) {
            return false;
        }
        boolean cur = false;
        if (prev < root.val) {
            cur = true;;
        }
        if (!cur) return false;
        // 更新 prev
        prev = root.val;
        boolean right = isValidBST(root.right);
        return left && cur && right;
    }

    int ret = 0;;
    int count = 0;

    /**
     * 二叉搜索树中第 k 小的元素
     * @param root
     * @param k
     * @return
     */
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        dfs1(root);
        return ret;
    }

    public void dfs1(TreeNode root) {
        // 递归出口
        if (root == null || count == 0) {
            return;
        }
        // 继续递归
        dfs1(root.left);
        count--;
        if (count == 0) {
            ret = root.val;
            return;
        }
        dfs1(root.right);
    }

    // 记录前驱
//    List<String> res = new ArrayList<>();
//
//    /**
//     * 二叉树的所有路径
//     * @param root
//     * @return
//     */
//    public List<String> binaryTreePaths(TreeNode root) {
//        dfs2(root, new StringBuilder());
//        return res;
//    }
//    public void dfs2(TreeNode root, StringBuilder path) {
//        StringBuilder prevPath = new StringBuilder(path);
//        prevPath.append(root.val);
//        // 递归出口
//        if (root.left == null && root.right == null) {
//            res.add(prevPath.toString());
//            return;
//        }
//        // 继续递归
//        prevPath.append("->");
//        if (root.left != null) dfs2(root.left, prevPath);
//        if (root.right != null) dfs2(root.right, prevPath);
//    }

    List<List<Integer>> res;
    List<Integer> path;
    boolean[] choices ;

    /**
     * 全排列
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        res = new ArrayList<>();
        path = new ArrayList<>();
        choices = new boolean[nums.length];
        dfs(nums);
        return  res;
    }
    public void dfs(int[] nums) {
        // 结束条件
        if (path.size() == nums.length) {
            // 添加结果
            res.add(new ArrayList<>(path));
            // 返回
            return;
        }
        // 遍历所有选择
        for (int i = 0; i < nums.length; i++) {
            if (!choices[i]) {
                // 当前条件下继续遍历
                path.add(nums[i]);
                choices[i] = true;
                dfs(nums);
                // 回溯
                choices[i] = false;
                path.remove(path.size() - 1);
            }
        }
    }

    /**
     * 子集
     * @param nums
     * @return
     */
    public List<List<Integer>> subsets(int[] nums) {
        res = new ArrayList<>();
        path = new ArrayList<>();
        dfs(nums, 0);
        return res;
    }
    public void dfs(int[] nums, int index) {
        // 结束条件
        if (index >= nums.length) {
            res.add(new ArrayList<>(path));
            return;
        }
        // 继续递归
        // 1. 选择当前元素
        path.add(nums[index]);
        dfs(nums, index + 1);
        // 回溯
        path.remove(path.size() - 1);
        // 2. 不选当前元素
        dfs(nums, index + 1);
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.hanota(new ArrayList<>(Arrays.asList(2, 1, 0)), new ArrayList<>(), new ArrayList<>());
    }
}
